#include <iostream.h>
#include <stdio.h>
#include <conio.h>
#include <iomanip.h>
#include <stdlib.h>

             //1  2  3  4  5
int row1[5] = {0 ,50,-1,10,-1};
int row2[5] = {50,0 ,-1,-1,20};
int row3[5] = {-1,-1,0 ,6 ,15};
int row4[5] = {10,-1,6 ,0 ,-1};
int row5[5] = {-1,20,15,-1,0 };

int* map[5] = {row1, row2, row3, row4, row5};
int** T;
int** H;

void display(int **data)
{       int i,j;
  for ( i=0; i<5; i++)
  {
    for ( j=0; j<5; j++)
    {
      cout <<setw(3) <<data[i][j]; // *(*(data+i)+j)
    }
    cout <<endl;
  }
  cout<<endl;
}

void main(void)
{        int i,j;
  clrscr();
  display(map);
  cout<< endl;

  T = new int*[5];
  for ( j = 0; j < 5; j++)
  {
    T[j] = new int[5];
  }
  H = new int*[5];
  for ( j = 0; j < 5; j++)
  {
    H[j] = new int[5];
  }

  for ( i=0; i<5; i++)
  {
    for ( j=0; j<5; j++)
    {
      T[i][j] = map[i][j];
      if (map[i][j] == -1)
      {
	H[i][j] = 0;
      }
      else
      {
	H[i][j] = j;
      }
    }
  }
  for ( i=0; i<5; i++)
  {
    for ( j=0; j<5; j++)
    {
      for (int k=0; k<5; k++)
      {
	if (i!=j && T[j][i]!=-1 && T[i][k]!=-1 && (T[j][k]==-1 || T[j][k]>T[j][i]+T[i][k]))
	{
	  H[j][k] = H[j][i];
	  T[j][k] = T[j][i] + T[i][k];
	}
      }
    }
  }
  display(T); cout<< endl;
  //display(H); cout<< endl;
  getch();
}

